প্রিমস অ্যালগরিদম (Prim's Algorithm)
প্রিমস অ্যালগরিদম একটি গ্রাফ অ্যালগরিদম যা একটি সংযোগযুক্ত, অপরিবর্তিত গ্রাফ থেকে মিনিমাম স্প্যানিং ট্রি (MST) খুঁজে বের করতে ব্যবহৃত হয়। মিনিমাম স্প্যানিং ট্রি হল একটি সাবগ্রাফ যা গ্রাফের সমস্ত নোডকে সংযুক্ত করে এবং মোট ওজন সর্বনিম্ন থাকে।
অ্যালগরিদমের বর্ণনা
প্রিমস অ্যালগরিদম নিম্নলিখিত ধাপগুলো অনুসরণ করে:
- একটি সূচনামূলক নোড নির্বাচন করুন।
- সেই নোডের সাথে সংযুক্ত সমস্ত এজ এবং নোডগুলিকে একটি সংগ্রহে যুক্ত করুন।
- সংযুক্ত নোডগুলির মধ্যে সর্বনিম্ন ওজনের এজ নির্বাচন করুন এবং সংশ্লিষ্ট নোডটিকে MST-তে যুক্ত করুন।
- নতুন নোডের সাথে সংযুক্ত এজ এবং নোডগুলোকে আবার সংগ্রহে যুক্ত করুন।
- ধাপ 3 এবং 4 পুনরাবৃত্তি করুন যতক্ষণ না সমস্ত নোড MST-তে যুক্ত হয়।
অ্যালগরিদমের উদাহরণ
ধরা যাক আমাদের একটি গ্রাফ রয়েছে:
(1)
/ | \
(2) (3) (4)
\ | /
(5)
এখানে, সংখ্যা গুলি নোড এবং তাদের মধ্যে লাইনগুলি এজ নির্দেশ করে। আমরা যেকোনো নোড থেকে শুরু করে প্রিমস অ্যালগরিদম ব্যবহার করে MST বের করবো।
প্রিমস অ্যালগরিদমের উদাহরণ কোড (Python):
import heapq
def prims_algorithm(graph, start):
mst = [] # মিনিমাম স্প্যানিং ট্রির জন্য
visited = set([start])
edges = [(cost, start, to) for to, cost in graph[start].items()]
heapq.heapify(edges)
while edges:
cost, frm, to = heapq.heappop(edges)
if to not in visited:
visited.add(to)
mst.append((frm, to, cost))
for to_next, cost in graph[to].items():
if to_next not in visited:
heapq.heappush(edges, (cost, to, to_next))
return mst
# গ্রাফের উদাহরণ
graph = {
'A': {'B': 1, 'C': 3, 'D': 4},
'B': {'A': 1, 'D': 2},
'C': {'A': 3, 'D': 1},
'D': {'A': 4, 'B': 2, 'C': 1}
}
mst = prims_algorithm(graph, 'A')
print("Minimum Spanning Tree:")
for frm, to, cost in mst:
print(f"{frm} - {to}: {cost}")
জটিলতা বিশ্লেষণ
- টাইম কমপ্লেক্সিটি: O(E log V), যেখানে E হল এজের সংখ্যা এবং V হল নোডের সংখ্যা। কারণ আমরা একটি মিন হিপ (min-heap) ব্যবহার করছি।
- স্পেস কমপ্লেক্সিটি: O(V + E)।
উপসংহার
প্রিমস অ্যালগরিদম একটি কার্যকরী এবং জনপ্রিয় পদ্ধতি যা মিনিমাম স্প্যানিং ট্রি বের করতে সাহায্য করে। এটি গ্রাফের বিভিন্ন অ্যাপ্লিকেশন, যেমন নেটওয়ার্ক ডিজাইন, পাওয়ার গ্রিড এবং অন্যান্য ক্ষেত্রে গুরুত্বপূর্ণ। এর সহজতর বাস্তবায়ন এবং কার্যকারিতা এই অ্যালগরিদমকে জনপ্রিয় করে তুলেছে।
Content added By
